1. Field of the Invention
This invention relates generally to the field of finite-state machines and, more particularly, to the implementation of a finite-state machine based on a content-addressable memory.
A finite-state machine is any device that can selectively assume any one of a finite plurality of states, that can change its state in response to its inputs and its current state, and that generates an output that depends at least on its stored state. It is usually described by a truth table that gives, for every possible combination of input and current state, what the output and next state will be.
In principle, of course, all digital circuits except purely combinatorial ones--i.e., all circuits that retain any "history"--are finite-state machines. However, the use of the term finite-state machine is used most commonly in connection with devices, such as sequencers and controllers, that are thought of most explicitly as sequencing through a plurality of states.
Finite-state machines of those types are often embodied programmable logic arrays (PLAs). FIG. 1 depicts an exemplary configuration of such a machine. The PLA 10 is a semi-custom array of gates containing fuses that can be blown to customize the array to achieve the desired Boolean relationship between the PLA input and the PLA output. For the sake of example, the PLA 10 is illustrated as receiving a forty-eight-bit input and generating a thirty-two-bit output.
The finite-state machine 12 of FIG. 1 receives as its input the DATA signal on lines 14 and generates its output on lines 16. At the beginning of each period of operation of the finite-state machine 12 there occurs a CLOCK1 pulse, which is followed by a CLOCK2 pulse. When the CLOCK1 pulse arrives, it causes two latches 18 and 20 to latch in the values of the signals at their input ports. The result is that the forty-eight-bit PLA input thereafter consists of the values that the DATA signals and sixteen bits of the PLA output represented when the CLOCK1 pulse arrived. That is, the PLA output depends not only on the last DATA input but also on the last output of the PLA, and this feedback of the last output is what gives the circuit its state characteristics.
The sixteen bits of the PLA output on lines 22 are those that are used as the machine output, and a further latch 24 latches those bits for presentation on lines 16 on the occurrence of CLOCK2, which occurs after the PLA outputs have settled.
The arrangement of FIG. 1 provides simplicity and economy, but it lacks flexibility, because the Boolean relationship between the PLA input and its output is fixed when the PLA is initially programmed: the PLA is not reprogrammable, and this can be a drawback in certain finite-state-machine applications, in which frequent reprogramming is necessary. To overcome this drawback, it has been proposed to employ a read/write random-access memory (RAM) to establish the relationship between input and output. The RAM essentially contains the finite-state-machine truth table: each RAM address is the concatenation of a machine output and a current machine state, and the content of each RAM location is the concatenation of the output and next state that should result from the input and current state that the output represents.
FIG. 2 depicts an example of such an arrangement. The fourteen address bits of a 16K.times.16 RAM are divided into seven next-state bits and seven bits of machine input, while the sixteen RAM output data bits are divided into nine bits of machine output and the seven bits of next-state information that the address input port receives.
Since the RAM is a read/write memory, this arrangement provides the reprogrammability that the PLA arrangement does not, and it is therefore a beneficial alternative in many situations in which reprogrammability is necessary. Unfortunately, the RAM arrangement is impractical for relatively large input-word sizes or very large numbers of states, since the necessary size of the RAM increases exponentially with both quantities. If the RAM approach were to be used for the word size and number of states assumed in connection with FIG. 1, for instance, the RAM size would have to be on the order of hundreds of trillions of thirty-two-bit locations. Few applications occur in which a memory of that size is practical.